package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
	Implement atoi to convert a string to an integer.
	
	Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
	
	Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
	
	Update (2015-02-10):
	The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button  to reset your code definition.
	
	spoilers alert... click to show requirements for atoi.
	
	Requirements for atoi:
	The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
	
	The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
	
	If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
	
	If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
	

题目大意
	字符串转为整数是很常用的一个函数，由于输入的是字符串，所以需要考虑的情况有很多种。我之前有一篇文章是关于验证一个字符串是否为数字的，参见 http://www.cnblogs.com/grandyang/p/4084408.html 。在那篇文章中，详细的讨论了各种情况，包括符号，自然数，小数点的出现位置，判断他们是否是数字。个人以为这道题也应该有这么多种情况。但是这题只需要考虑数字和符号的情况：
	
	1. 若字符串开头是空格，则跳过所有空格，到第一个非空格字符，如果没有，则返回0.
	
	2. 若第一个非空格字符是符号+/-，则标记sign的真假，这道题还有个局限性，那就是在c++里面，+-1和-+1都是认可的，都是-1，而在此题里，则会返回0.
	
	3. 若下一个字符不是数字，则返回0. 完全不考虑小数点和自然数的情况，不过这样也好，起码省事了不少。
	
	4. 如果下一个字符是数字，则转为整形存下来，若接下来再有非数字出现，则返回目前的结果。
	
	5. 还需要考虑边界问题，如果超过了整形数的范围，则用边界值替代当前值。
解题思路
	TODO:日狗啊！！！！！！！！！！！！！！！！！	+-2要返回0
 * @Date 2017-09-15 13：16
 */
public class _008_String_to_Integer_atoi {
	
	public int myAtoi(String str) {
    	if (str==null || str.equals(""))	return 0;
    	//看下该字符串是否包含数字
    	boolean isIncludeNum = false;
    	for (int i = 0; i < str.length(); i ++) {
    		if(str.charAt(i) >= '0' && str.charAt(i) <= '9')	isIncludeNum = true;	
    	}
    	
    	if (!isIncludeNum)	return 0;
    	
    	//去掉头尾空格
    	str = str.trim();
    	boolean positive = true;		//符号 true..正, false..负
    	/**
    	 * 存在一种可能
    	 * eg : +-+-+-2=2 (妈的智障。。。)
    	 */
    	int sign = 0, start = 0;			//start..字符串开始遍历的索引(字符串第一个数字出现的索引)
    	if (str.charAt(0)=='+' || str.charAt(0)=='-') {
    
    		while (str.charAt(start)=='+' || str.charAt(start)=='-') {
    			if (str.charAt(start++) == '-') sign--;
    			else sign++;
    		}
    		positive = sign<0?false:true;
    	}
    	
    	int rs = 0;
    	int N  = str.length();
    	//i：遍历字符串 ：不存在符号从0索引开始遍历,存在符号从1索引开始遍历
    	for (int i  = start; i < N; i ++) {
    		char curCh = str.charAt(i);
    		int curNum = char2num(curCh);
    		//检查是否越界
    		if (positive && rs*10+curNum>Integer.MAX_VALUE)	return Integer.MAX_VALUE;
    		if (positive && rs*10-curNum<Integer.MIN_VALUE)	return Integer.MIN_VALUE;
    		//计算
    		if (positive)
    			rs = rs*10+curNum;
    		else rs = rs*10-curNum;
    	}
		return rs;
    }
    
    private Integer char2num(Character ch) {
		return ch - '0';
	}
	
	   public int myAtoi2(String str) {
	        if (str.isEmpty()) return 0;
	        int sign = 1, base = 0, i = 0, n = str.length();
	        while (i < n && str.charAt(i) == ' ') ++i;
	        if (str.charAt(i) == '+' || str.charAt(i) == '-') {
	            sign = (str.charAt(i++) == '+') ? 1 : -1;
	        }
	        while (i < n && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
	            if (base > Integer.MAX_VALUE / 10 || (base == Integer.MAX_VALUE / 10 && str.charAt(i) - '0' > 7)) {
	                return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
	            }
	            base = 10 * base + (str.charAt(i++) - '0');
	        }
	        return base * sign;
	    }	
    public static void main(String[] args) {
		_008_String_to_Integer_atoi obj = new _008_String_to_Integer_atoi();
//		obj.twoSum(new int[]{1, 2, 3, 4, 5, 6, 7}, 7);
//		obj.twoSum2(new int[]{2, 7, 11, 15}, 9);
		LogUtils.println("结果", obj.myAtoi2("+-+2"));
//		LogUtils.println("结果",Integer.valueOf("+-2"));
	}

}
